package exampleQuestions;

import java.util.LinkedList;
import java.util.List;

public class ParentThesisGenerator {

	/**
	 * 
	 * given a value 'N', generate all possible valid combinations of
	 * parentheses. example: N=2 valid parentheses: ()(), (()) 9
	 */
	public static void main(String[] args) {

		int num = 7;

		List<String> list = generateParenthesis(num);

		for (String s : list) {
			System.out.println(s);
		}

	}

	private static List<String> generateParenthesis(int num) {

		if (num < 0) {
			return null;
		}
		
		List<String> list = new LinkedList<String>();
		
		generate(0, 0, num, new StringBuilder(), list);

		return list;
	}

	private static void generate(int left, int right, int total, StringBuilder sb, List<String> list) {
		
		if (left < total) {
			generate(left+1, right, total, new StringBuilder(sb.toString() + "("), list);
		}
		
		if (right < left && right < total) {
			generate(left, right+1, total, new StringBuilder(sb.toString() + ")"), list);
		}
		
		if (left == total && right == total) {
			list.add(sb.toString());
		}
		
	}
}
